#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <set>
#include <utility>
#include <iterator>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>

using namespace std;

typedef pair< string, string > Ticket;

ostream &operator<<( ostream &o, Ticket const &ticket ) {
    return o << ticket.first << " -> " << ticket.second;
}

template <class ForwardIterator>
Ticket resolve( ForwardIterator it, ForwardIterator end ) {
    typedef map< string, int > Counter;
    Counter ctr;
    for ( ; end != it; it++ ) {
	// could be further 'optimized' by using ctr.lower_bound?
	ctr[it->first] |= 2;
	if ( ctr[it->first] == 3 ) ctr.erase(it->first);
	ctr[it->second] |= 1;
	if ( ctr[it->second] == 3 ) ctr.erase(it->second);
    }
    Ticket result;
    for ( Counter::const_iterator it = ctr.begin();
	  ctr.end() != it; it++ ) {
	if ( 2 == it->second ) {
	    assert( result.first == "" );
	    result.first = it->first; 
	}
	if ( 1 == it->second ) {
	    assert( result.second == "" );
	    result.second = it->first; 
	}
    }
    return result;
}

string createName( unsigned len = 3 ) {
    string result;
    for ( int i = 0; i < len; i++ ) {
	result += (unsigned)'A' + rand()%26;
    }
    return result;
}

template < class ForwardIterator >
void print_tickets( ostream &o, ForwardIterator it, ForwardIterator end ) {
    while ( it != end ) {
	o << *it++ << endl;
    }
    o << endl;
}

int main ( int argc, char *argv[] ) {
    // srand( time( NULL ) );
    const unsigned count = 100;
    vector< Ticket > tickets;
    {
	set< string > tmp;
	while ( tmp.size() < count ) {
	    tmp.insert( createName() ) ;
	}
	vector< string > dests(count);
	copy( tmp.begin(), tmp.end(), dests.begin() );
	random_shuffle( dests.begin(), dests.end() );
	string prev = dests.back(); dests.pop_back();
	for ( vector<string>::const_iterator it = dests.begin();
	      dests.end() != it; it++ ) {
	    tickets.push_back( Ticket( prev, *it ) );
	    prev = *it;
	}
    }
    cout << "Resolved: " << Ticket( tickets.front().first, tickets.back().second ) << endl;
    random_shuffle( tickets.begin(), tickets.end() );
    cout << "Resolved: " << resolve( tickets.begin(), tickets.end() ) << endl;
    return 0;
}
